#pragma once
#ifndef HIGH_PRECISION_H
#define HIGH_PRECISION_H

#include <string>
#include <cmath>

// 高精度加法：carry计数进位
int add_high_precision(std::string a, std::string b)
{
    int an[505] = {0};
    int bn[505] = {0};
    int cn[505] = {0};
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    for (int i = 0; i < a.size(); i++) an[i] = a[i] - '0';
    for (int i = 0; i < b.size(); i++) bn[i] = b[i] - '0';

    int carry = 0;
    int index = a.size() > b.size() ? a.size() : b.size();
    for (int i = 0; i < index || carry; i++)
    {
        cn[i] = an[i] + bn[i] + carry;
        carry = cn[i] > 9 ? 1 : 0;
        if (carry) cn[i] %= 10;
    }
    while (index > 0 && cn[index] == 0) index--;
    for (int i = index; i >= 0; i--) printf("%d", cn[i]);
    printf("\n");
    return 0;
}

// 高精度减法：包含小于零的情况
void down_zero_high_precision(std::string inta, std::string intb)
{
    int an[10090] = {0}, bn[10090] = {0}, cn[10090] = {0};
    bool flag = 0;
    if (inta.size() < intb.size() || (inta.size() == intb.size() && inta < intb))
    {
        swap(inta, intb);
        flag = 1;
    }
    reverse(inta.begin(), inta.end()); reverse(intb.begin(), intb.end()); 
    for (int i = 0; i < inta.size(); i++) an[i] = inta[i] - '0';
    for (int i = 0; i < intb.size(); i++) bn[i] = intb[i] - '0';

    int index = inta.size() > intb.size() ? inta.size() : intb.size();
    for (int i = 0; i < index; i++)
        cn[i] = an[i] - bn[i];
    for (int i = 0; i < index; i++)
    {
        if (cn[i] < 0)
        {
            cn[i] += 10;
            cn[i + 1]--;
        }
    }
    if (flag) printf("-");
    while (index > 0 && cn[index] == 0) index--;
    for (int i = index; i >= 0; i--) printf("%d", cn[i]);
    printf("\n");
    return;
}

// 高精度乘法：高精度*低精度：计算2^n
void high_mult_low_precision2n(int n, int index = 1)
{
    unsigned int a[105] = {1};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < index; j++) 
        {
            a[j] *= 2;
        }
        for (int j = 0; j < index; j++) 
        {
            a[j + 1] += a[j] / 10;
            a[j] %= 10;
        }
        
        while (a[index] > 0) index++;
    }
    for (int i = index - 1; i >= 0; i--) printf("%d", a[i]);
    printf("\n");
    return;
}

// 高精度乘法：高精度*低精度：计算n!
void high_mult_low_precision_n1(int n, int index = 1)
{
    unsigned int a[10000005] = {1};
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < index; j++) 
        {
            a[j] *= i;
        }
        for (int j = 0; j < index - 1; j++) 
        {
            a[j + 1] += a[j] / 10;
            a[j] %= 10;
        }
        
        while (a[index- 1] > 9)
        {
            a[index] = a[index - 1] / 10;
            a[index - 1] %= 10;
            index++;
        }
    }
    for (int i = index - 1; i >= 0; i--) printf("%d", a[i]);
    printf("\n");
    return;
}

// 高精度乘法：高精度*高精度模板
void high_mult_high_precision(std::string s1, std::string s2)
{
    int a[2005] = {0}, b[2005] = {0}, c[2005] = {0}; //c数组范围会导致出现越界问题
    int len1 = s1.size(), len2 = s2.size();
    int len = len1 + len2;
    for (int i = 0; i < len1; i++) a[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++) b[i] = s2[len2 - i - 1] - '0';
 
    for (int i = 0; i < len1; i++)
    {
        for (int j = 0; j < len2; j++)
        {
            c[i + j] += a[i] * b[j];
        }
    }

    for (int i = 0; i < len - 1; i++)
    {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }

    while (c[len - 1] > 9)
    {
        c[len] = c[len - 1] / 10;
        c[len - 1] %= 10;
        len++;
    }
    while (len > 1 && c[len - 1] == 0) len--;
    for (int i = len - 1; i >= 0; i--) printf("%d", c[i]);
    printf("\n");
    return;
}

#endif